The present application relates generally to an improved data processing apparatus and method and more specifically to an apparatus and method for updating shared variables atomically.
In multi-threaded and multiple processor data processing systems, several threads or processing units may access a common shared memory. In a shared memory system, a thread will typically load a portion of data into cache from a source address. The thread sets a lock on that source address to preserve the illusion of atomicity and to maintain data integrity. In an atomic transaction, a series of operations either all occur or nothing occurs. A guarantee of atomicity prevents updates to the database occurring only partially, which can cause greater problems than rejecting the whole series outright. A lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution.
A cache is used to speed up data transfer and may be either temporary or permanent. Memory caches are in every computer to speed up instruction execution and data retrieval and updating. These temporary caches serve as staging areas, and their contents are constantly changing. A memory cache, or “CPU cache,” is a memory bank that bridges main memory and the central processing unit (CPU). A memory cache is faster than main memory and allows instructions to be executed and data to be read and written at higher speed. Instructions and data are transferred from main memory to the cache in fixed blocks, known as cache “lines.”
In a typical transaction, a thread may acquire a lock on the granularity of the address, read a variable from the address, perform work and update the variable, and release the lock. Often, a thread may acquire a lock on a first address, read a first variable, acquire a lock on a second address, and read a second variable. This may result in a possible deadlock situation where a second thread acquires a lock on the second address and then attempts to acquire a lock on the first address. A deadlock is a situation where two or more competing actions are waiting for the other to finish, and thus neither ever does. Thus, in the above example, the first thread cannot acquire the lock on the second address, and the second thread cannot acquire the lock on the first address. A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.
A multi-threaded and/or multiple processor data processing system may service many transactions simultaneously, and each thread may take many cycles to complete one transaction. Each thread must preserve the illusion of atomicity to prevent other transactions from seeing out-of-date information or directories in an inconsistent state due to partial update.